/**
 * @program: LeetCode
 * @description: LeetCode : 235. 二叉搜索树的最近公共祖先
 * @author: WXY
 * @create: 2023-01-05 11:28
 * @Version 1.0
 **/
public class Num235_lowestCommonAncestor {
    public static TreeNode lowestCommonAncestor1(TreeNode root, TreeNode o1, TreeNode o2) {
        Info res = process(root, o1, o2);
        return res.ans;
    }

    private static Info process(TreeNode x, TreeNode o1, TreeNode o2) {
        if (x == null) {
            return new Info(false, false, null);
        }
        Info leftInfo = process(x.left, o1, o2);
        Info rightInfo = process(x.right, o1, o2);
        boolean isFindO1 = x.val == o1.val || leftInfo.isFindO1 || rightInfo.isFindO1;
        boolean isFindO2 = x.val == o2.val || leftInfo.isFindO2 || rightInfo.isFindO2;

        TreeNode ans = null;
        if (isFindO1 && isFindO2) {
            if (leftInfo.ans == null && rightInfo.ans == null) {
                ans = x;
            }
            if (leftInfo.ans != null && rightInfo.ans == null) {
                ans = leftInfo.ans;
            }
            if (leftInfo.ans == null && rightInfo.ans != null) {
                ans = rightInfo.ans;
            }
        }
        return new Info(isFindO1, isFindO2, ans);
    }

    public static void main(String[] args) {
        TreeNode head = new TreeNode(6);
        head.left = new TreeNode(2);
        head.right = new TreeNode(8);
        head.left.left = new TreeNode(0);
        head.left.right = new TreeNode(4);
        head.left.right.left = new TreeNode(3);
        head.left.right.right = new TreeNode(5);
        head.right.right = new TreeNode(9);
        head.right.left = new TreeNode(7);
        TreeNode treeNode = lowestCommonAncestor1(head, new TreeNode(3), new TreeNode(5));
        System.out.println(treeNode.val);

    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public static class Info {
        boolean isFindO1;
        boolean isFindO2;
        TreeNode ans;

        public Info(boolean isFindO1, boolean isFindO2, TreeNode ans) {
            this.isFindO1 = isFindO1;
            this.isFindO2 = isFindO2;
            this.ans = ans;
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode o1, TreeNode o2) {
        if (root.val > o1.val && root.val > o2.val) {
            return lowestCommonAncestor(root.left, o1, o2);
        }
        if (root.val < o1.val && root.val < o2.val) {
            return lowestCommonAncestor(root.right, o1, o2);
        }
        return root;
    }


}
